{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## **实验五  栈的实现**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 实验要求:1-建立顺序栈,实现栈的基本操作.2-完成用以实现10进制数转换成任意进制(2~9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1-1,建立顺序栈"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack(object):\n",
    "    def __init__(self):\n",
    "        self.stack = []\n",
    "\n",
    "    def push(self,item):    # 元素进栈\n",
    "        self.stack.append(item)\n",
    "\n",
    "    def pop(self):  # 从栈顶删除item\n",
    "        if self.stack:\n",
    "            return self.stack.pop()\n",
    "        else:\n",
    "            raise LookupError('栈为空')\n",
    "\n",
    "    def isEmpty(self): # 如果栈为空\n",
    "        return self.stack == []\n",
    "\n",
    "    def peek(self):    #查看栈顶元素\n",
    "        return self.stack[-1]\n",
    "    \n",
    "    def size(self):    # 查看栈大小\n",
    "        return len(self.stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1-2,实现栈的基本操作"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 初始化栈\n",
    "s = Stack()\n",
    "# 判断栈空\n",
    "s.isEmpty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 元素入栈\n",
    "s.push(4)\n",
    "s.push('dog')\n",
    "s.push(True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 查看栈顶元素\n",
    "s.peek()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 删除栈顶元素并再次查看栈顶元素\n",
    "s.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 入栈并查看栈大小\n",
    "s.push('cat')\n",
    "s.push(2)\n",
    "s.size()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2,进制转换"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BaseConversion(num,base):\n",
    "    stack = Stack()\n",
    "    digits = \"0123456789ABCDEF\"\n",
    "    while num >0:\n",
    "        remainder = num % base\n",
    "        stack.push(remainder)\n",
    "        num //= base\n",
    "    BaseString = \"\"\n",
    "    while not stack.isEmpty():\n",
    "        BaseString = BaseString + digits[stack.pop()]\n",
    "    return  BaseString\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "请输入要转换的数值: 1000\n",
      "请问要转换成几进制? 16\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000转换成16进制后的数值为: 3E8\n"
     ]
    }
   ],
   "source": [
    "num = int(input('请输入要转换的数值:'))\n",
    "base = int(input('请问要转换成几进制?'))\n",
    "print('{}转换成{}进制后的数值为:'.format(num,base),BaseConversion(num,base))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## **实验六  栈的应用举例**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "实验要求：1、建立一个顺序栈，实现括号配对，判断一个表达式中括号配对是否合法。2、当用户输入一个合法的表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的数要求在实数范围内。对于异常表达式给出错误提示。（要求使用静态栈数据结构）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 1、括号匹配"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dict_values(['{', '(', '[']) dict_keys(['}', ')', ']'])\n"
     ]
    }
   ],
   "source": [
    "bracket_stack = Stack()   # 实例化括号匹配栈\n",
    "BRACKET = {'}': '{', ')': '(', ']': '['}   \n",
    "BRACKET_L, BRACKET_R = BRACKET.values(), BRACKET.keys()\n",
    "print(BRACKET_L,BRACKET_R)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Check_bracket(s):   # 括号匹配函数\n",
    "    for c in s:\n",
    "        if c in BRACKET_L:\n",
    "            # 左括号入栈\n",
    "            bracket_stack.push(c)\n",
    "        elif c in BRACKET_R:\n",
    "            # 右括号，要么栈顶元素出栈，要么匹配失败\n",
    "            if bracket_stack.isEmpty() == False and bracket_stack.peek() == BRACKET[c]:\n",
    "                bracket_stack.pop()\n",
    "            else:\n",
    "                return '括号匹配失败'\n",
    "    if bracket_stack.isEmpty() == False:  # 如果输入的右括号数量少于左括号，导致左部分左括号仍然在栈中得不到匹配\n",
    "        return '输入的右括号数量少于左括号'\n",
    "    return '括号匹配成功'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "请输入表达式： 3 * {3 +[(2 -3) * (4+5)]}\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "表达式括号匹配是否合法： 括号匹配成功\n"
     ]
    }
   ],
   "source": [
    "s1 = input(\"请输入表达式：\")\n",
    "print('表达式括号匹配是否合法：',Check_bracket(s1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "请输入表达式： 3 * {3 +[(2 -3) * (4+5)]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "表达式括号匹配是否合法： 输入的右括号数量少于左括号\n"
     ]
    }
   ],
   "source": [
    "s2 = input(\"请输入表达式：\")\n",
    "print('表达式括号匹配是否合法：',Check_bracket(s2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "请输入表达式： 3 * {3 +[(2 -3) * (4+5)]]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "表达式括号匹配是否合法： 括号匹配失败\n"
     ]
    }
   ],
   "source": [
    "s3 = input(\"请输入表达式：\")\n",
    "print('表达式括号匹配是否合法：',Check_bracket(s3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2、表达式计算"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluator(expression : str) -> int :\n",
    "    # 字符串转化为列表\n",
    "    token_list = list(expression)  \n",
    "    # 运算符优先级字典\n",
    "    pre_dict = {'*':3,'/':3,'+':2,'-':2,'(':1}\n",
    "    # 运算符栈\n",
    "    symbol_stack = Stack()\n",
    "    # 操作数栈\n",
    "    num_stack = Stack()\n",
    "    for token in token_list:\n",
    "        # 数字进操作数栈\n",
    "        if token.isdecimal() or token[1:].isdecimal():\n",
    "            num_stack.push(int(token))\n",
    "        # 左括号进运算符栈\n",
    "        elif token == '(':\n",
    "            symbol_stack.push(token)\n",
    "        # 碰到右括号，就要把栈顶的左括号上面的运算符都弹出求值\n",
    "        elif token == ')':\n",
    "            top = symbol_stack.pop()\n",
    "            while top != '(':\n",
    "                # 每弹出一个运算符，就要弹出两个操作数来求值\n",
    "                # 注意弹出操作数的顺序是反着的，先弹出的数是op2\n",
    "                op2 = num_stack.pop()\n",
    "                op1 = num_stack.pop()\n",
    "                # 求出的值要压回操作数栈\n",
    "                # 这里用到的函数get_value在下面有定义\n",
    "                num_stack.push(get_value(top,op1,op2))\n",
    "                # 弹出下一个栈顶运算符\n",
    "                top = symbol_stack.pop()\n",
    "        # 碰到运算符，就要把栈顶优先级不低于它的都弹出求值\n",
    "        elif token in '+-*/':\n",
    "            while symbol_stack.isEmpty() == False and pre_dict[symbol_stack.peek()] >= pre_dict[token]:\n",
    "                top = symbol_stack.pop()\n",
    "                op2 = num_stack.pop()\n",
    "                op1 = num_stack.pop()\n",
    "                num_stack.push(get_value(top,op1,op2))\n",
    "            # 别忘了最后让当前运算符进栈\n",
    "            symbol_stack.push(token)\n",
    "    # 表达式遍历完成后，栈里剩下的操作符也都要求值   \n",
    "    while symbol_stack.isEmpty() == False:\n",
    "        top = symbol_stack.pop()\n",
    "        op2 = num_stack.pop()\n",
    "        op1 = num_stack.pop()\n",
    "        num_stack.push(get_value(top,op1,op2))\n",
    "    # 返回最后数字栈的值\n",
    "    return num_stack.peek()\n",
    " \n",
    "def get_value(operator : str, op1 : int, op2 : int):\n",
    "    if operator == '+':\n",
    "        return op1 + op2\n",
    "    elif operator == '-':\n",
    "        return op1 - op2\n",
    "    elif operator == '*':\n",
    "        return op1 * op2\n",
    "    elif operator == '/':\n",
    "        return op1 / op2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "请输入表达式： 2+2*(2+2)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "计算结果为： 10\n"
     ]
    }
   ],
   "source": [
    "s1 = str(input('请输入表达式：'))\n",
    "print('计算结果为：',evaluator(s1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "请输入表达式： 2+4-6/(3+3)-1\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "计算结果为： 4.0\n"
     ]
    }
   ],
   "source": [
    "s2 = str(input('请输入表达式：'))\n",
    "print('计算结果为：',evaluator(s2))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
